package com.copa.l90;

import java.util.*;

/**
 * @author copa
 * @createDate 2022-05-18 10:34
 * @function 排序+回溯法（DFS）
 */
public class Test1 {

    public List<List<Integer>> subsetsWithDup(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        Arrays.sort(nums);
        dfs(nums, result, 0, new ArrayList<>());
        return result;
    }

    private void dfs(int[] nums, List<List<Integer>> result, int startIndex, ArrayList<Integer> tempList) {
        // 由于是深度优先遍历，直接添加即可
        result.add(new ArrayList<>(tempList));
        for (int i = startIndex; i < nums.length; i++) {
            if (i > startIndex && nums[i] == nums[i - 1]) {
                // 这里巧妙就在这里，如果遍历的这个元素等于上一个元素，则直接继续下一次遍历了，就不用像我那样做标记了
                continue;
            }
            // 回溯并剪枝
            tempList.add(nums[i]);
            dfs(nums, result, i + 1, tempList);
            tempList.remove(tempList.size() - 1);
        }
    }

    /**
     * 下面是我自己的解法 复杂化了用了map来标记
     * @param nums
     * @return
     */
    public List<List<Integer>> subsetsWithDup2(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        // 标记法，因为涉及到元素重复去重
        HashMap<List<Integer>, Boolean> map = new HashMap<>();
        // 先给nums排序
        Arrays.sort(nums);
        dfs2(nums, result, 0, map, new ArrayList<>());
        return result;
    }

    private void dfs2(int[] nums,
                     List<List<Integer>> result,
                     int startIndex,
                     HashMap<List<Integer>, Boolean> flag,
                     ArrayList<Integer> tempList) {
        if (Objects.isNull(flag.get(tempList))) {
            // 如果是新元素，则应该加入到排重map里
            flag.put(tempList, false);
        }
        if (!flag.get(tempList)) {
            // 若map中为false，则是结果集所没有的，所以要加到结果集中
            result.add(new ArrayList<>(tempList));
            // 设置这个已经加入到结果集中
            flag.put(tempList, true);
        }
        for (int i = startIndex; i < nums.length; i++) {
            tempList.add(nums[i]);
            // 回溯并剪枝
            dfs2(nums, result, ++startIndex, flag, tempList);
            // 惨案
            // 如果用了这个，startIndex仍然是0，这个涉及到jvm的
            //backTracking(nums, result, startIndex + 1, flag, tempList);
            tempList.remove(tempList.size() - 1);
        }
    }

    public static void main(String[] args) {
        int[] nums = new int[]{1, 2, 2};
        List<List<Integer>> result = new Test1().subsetsWithDup(nums);
        for (List<Integer> list : result) {
            System.out.println(Arrays.toString(list.toArray()));
        }
    }

}
